package com.bee.剑指offer;

import java.util.Arrays;
import java.util.Random;

/**
 * @version 1.0.0
 * @Author yong.Mr
 * @data 2021-03-13
 */
public class 快速排序 {

    public static void quickSort(int[] array, int left, int rigth) {
        if (left > rigth) {
            return;
        }
        int base = array[left];
        int low = left;
        int high = rigth;
        while (low != high) {
            // 从右向左检索，小的数
            while (array[high] >= base && low < high) {
                high--;
            }
            // 从左到右检索比base大的，
            while (array[low] <= base && low < high) {
                low++;
            }
            int temp = array[low];
            array[low] = array[high];
            array[high] = temp;
        }
        // 将基数和low=high相遇位置的数交换
        array[left] = array[low];
        array[low] = base;
        // 递归调用，分别先对基数的左区间，进排序，再右区间进行排序
        quickSort(array, left, low - 1);
        quickSort(array, low + 1, rigth);

    }

    public static void main(String[] args) {
        int[] array = new int[8];
		/*int[] destArray = moBaoPaiXu(array);
		System.out.println("冒泡排序之后的数据:" + Arrays.toString(destArray));*/
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(50);
        }
        quickSort(array, 0, array.length - 1);
        System.out.println("快速排序之后的数据:" + Arrays.toString(array));
    }
}
